UVa/11512 - GATTACA/gattaca.3.cpp

   1 /*
   2   Problem: G - GATTACA
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6   Slow. Takes ~14 seconds on 100 hundred strings of length 1000.
   7  */
   8
   9 using namespace std;
  10 #include <algorithm>
  11 #include <iostream>
  12 #include <iterator>
  13 #include <sstream>
  14 #include <fstream>
  15 #include <cassert>
  16 #include <climits>
  17 #include <cstdlib>
  18 #include <cstring>
  19 #include <string>
  20 #include <cstdio>
  21 #include <vector>
  22 #include <cmath>
  23 #include <queue>
  24 #include <deque>
  25 #include <stack>
  26 #include <map>
  27 #include <set>
  28
  29 #define D(x) cout << #x " is " << x << endl
  30
  31 inline int v(char c){if(c=='A')return 0;if(c=='C')return 1;if(c=='G')return 2;if(c=='T')return 3;};
  32
  33 struct node{
  34   int info;
  35   node * sons[4];
  36   node(int i = 0) : info(i){ sons[0] = sons[1] = sons[2] = sons[3] = NULL; }
  37 };
  38
  39 void clean(node * &u){
  40   if (u != NULL){
  41     for (int i=0; i<4; ++i) clean(u->sons[i]);
  42     delete u;
  43     u = NULL;
  44   }
  45 }
  46
  47 int main(){
  48   //freopen("gattaca.in", "r", stdin);
  49   int T;
  50   cin >> T;
  51   while (T--){
  52     string s;
  53     cin >> s;
  54     int n = s.size(), rep = 0;
  55     string ans = "";
  56
  57     node* root = new node;
  58
  59     for (int i=0; i<n; ++i){
  60         node * foot = root; //Tells me where i'm standing.
  61         string so_far = "";
  62         so_far.reserve(1000);
  63         for (int j=i; j < n; ++j){
  64           so_far = s.substr(i, j-i+1);
  65           if (foot->sons[v(s[j])] == NULL) foot->sons[v(s[j])] = new node;
  66           foot = foot->sons[v(s[j])];
  67           int t = ++foot->info;
  68           if (t > 1 && (so_far.size() > ans.size() || (so_far.size() == ans.size() && so_far < ans))){
  69             ans = so_far;
  70             rep = t;
  71           }
  72         }
  73       }
  74            if (rep == 0) cout << "No repetitions found!\n";
  75            else cout << ans << " " << rep << endl;
  76          clean(root);
  77   }
  78   return 0;
  79 }